package com.localking.algorithm.leetcode.array.string

/**
 * Write a function to find the longest common prefix string amongst an array of strings.
 * If there is no common prefix, return an empty string "".
 *
 * Example 1:
 * Input: ["flower", "flow", "flight"]
 * Output: "fl"
 *
 * Example 2:
 * Input: ["dog", "racecar", "car"]
 * Output: ""
 * Explanation: There is no common prefix among the input strings.
 *
 * Note:
 * All given inputs are in lowercase letters a-z.
 *
 * @author jinbo
 */
object LongestCommonPrefix {

  def main(args: Array[String]): Unit = {
    val strs = Array("flower", "flow", "flight")
    println(longestCommonPrefix(strs))
  }

  def longestCommonPrefix(strs: Array[String]): String = {
    if(strs.isEmpty) {
      return ""
    }
    val smallestSize = strs.map(str => str.length).min
    for(i <- 0 until smallestSize) {
      val char = strs(0)(i)
      for(str <- strs) {
        if(str(i) != char) {
          return strs(0).substring(0, i)
        }
      }
    }
    strs(0).substring(0, smallestSize)
  }
}
